The present invention relates to a technique for generating a hash value by use of data having an arbitrary finite length and to an application technique of the same.
In signature creation and user authentication using a public key encryption technique, it is required to create a random number uniquely corresponding to an input. A method which is employed for this purpose and which creates a fixed-length random number (hash value) by use of data having an arbitrary finite length is referred to as a hash function.
It is necessary for the hash function to meet safety requirements such as a one-way property (an input corresponding to a given output can not be found) and a strongly collision-free property (mutually different two inputs which lead to one and the same output can not be found). Also, in order that the hash function is applicable to practical uses, the hash function is required to be processed at a high speed when it is implemented in the form of software or hardware. In addition, it is required to be efficient in the implementation cost. That is, when the hash function is implemented in the form of hardware, the number of required gates is small; when the hash function is implemented in the form of software, the number of steps and the memory area required in execution of the software are small.
A general encryption algorithm desirably satisfies these evaluation items at a high level.
In general, a hash function includes a compression function to process a fixed-length input. By repeatedly executing processing based on the compression function, input data having an arbitrary length is compressed and is randomized to finally produce a hash value as an output. Representative examples of a hash function is SHA-1, SHA-256, and Whirlpool (pages 13 to 15 and 19 to 22 of “ISO/IEC 10118-3 third edition Information technology-Security-techniques-Hash-functions” published on Mar. 1, 2004 in Switzerland; to be referred to as article 1).
A method of repeatedly executing the compression function which is employed in SHA-1, SHA-256, and Whirlpool described in article 1 is referred to as Merkle-Damgaard Strengthening. In this method, input data is divided into fixed-length data items (each data item thus divided is called a block) such that an output for a preceding block, i.e., an intermediate hash value and an input data block are used as inputs to the compression function to generate a next intermediate hash value.